The Garbage Collector

The garbage collector of KCL has three levels according to what it collects:

1. cells
2. cells and relocatable blocks
3. cells, relocatable blocks and contiguous blocks.

In levels 2 and 3, the relocatable area is shifted to the higher address space to reserve an appropriate number of pages in the hole.

For each type class, KCL keeps a free list of unused cells, and when the free list is exhausted, a new page is allocated, or the garbage collector is invoked, depending on whether the maximum number of pages for that class have been allocated or not.

The garbage collector does not compactify the heap. That is, cells and contiguous blocks are never moved to another place. Moreover, once a page is allocated for a particular type class or for contiguous blocks, that page will never be freed for other classes, even if the entire page becomes garbage.

On the other hand, the relocatable area is compactified during level 2 and level 3 of garbage collection. A relocatable block is really relocatable.

The garbage collector is automatically invoked in one of the following situations. The number in the parentheses indicates the level of garbage collection that is performed.

*

The free list of a certain type class is exhausted after the maximum number of pages have been allocated for that type class (1).

*

The hole is exhausted (2).

*

The relocatable area is exhausted after the maximum number of pages have been allocated for the relocatable area (2).

*

The contiguous blocks are exhausted after the maximum number of pages have been allocated for contiguous blocks (3).

The garbage collector is also invoked by the following KCL specific function.

gbc x[Function]

The garbage collector is invoked with the level specified by x. If x is nil, the garbage collector is invoked for level 1 garbage collection. If x is t, it is invoked for level 3 garbage collection. Otherwise, it is invoked for level 2 garbage collection.